1. Field of the Invention
The present invention relates to motion estimation methods and apparatuses used in a digital moving picture compression system, and more particularly to a motion estimation method and an apparatus capable of performing motion estimation with a small amount of computation.
2. Description of the Background Art
A motion estimation apparatus is used in a moving picture compression system for MPEG (Moving Picture Experts Group) and performs a large number of computations. To date, various computation algorithms for the motion estimation apparatus have been proposed. For the moving picture compression system for MPEG, xe2x80x9cVLSI Architectures for Video Compressionxe2x80x94A Surveyxe2x80x9d, by P. Pirsch et al., Proc. IEEE Vol. 83, No. 2, pp. 220-246, 1995 and xe2x80x9cULSI Realization of MPEG2 Realtime Video Encoder and Decoderxe2x80x94An Overviewxe2x80x9d, by M. Yoshimoto et al., IEICE Trans. Electron., Vol. E78-C, No. 12, pp. 1668-1681, 1995 are incorporated herein by reference.
In addition, for an LSI (Large Scale Integration) for motion estimation computation, xe2x80x9cA Half-pel Precision MPEG2 Motion-Estimation Processor with Concurrent Threexe2x80x94Vector Searchxe2x80x9d, by K. Ishihara et al., ISSCC Digest of Technical Papers, pp. 1502-1509, 1995 and xe2x80x9cA Motion Estimation Processor for MPEG2 Video Real Time Encoding at Wide Search Rangexe2x80x9d, by A. Ohtani et al., Proc. IEEE Custom Integrated Circuits Conference, pp. 405-408, 1995 are incorporated herein by reference.
A full search method for all samples is conventionally known as the motion estimation method. This is a method for performing a difference calculation of corresponding sample values of one of blocks to be searched and a reference block in every position within a block for every candidate vector in a search range. The method allows correct detection of a vector in a position of a minimum difference value.
However, the full search method for all samples requires a large amount of computation, so that the search range for the vector which can be implemented by a single LSI is limited. Accordingly, the method disadvantageously requires a large number of LSIs to search over a large range. A subsample method has been proposed which performs the difference calculation for some of the positions in each search range for reducing the amount of difference calculation. In addition, an algorithmic search method has been proposed which selects a search position in a search range in accordance with a specific algorithm for performing a difference calculation of one of blocks to be searched and a reference block only for some of search positions. Moreover, various methods have been proposed for searching over a larger search range with a smaller amount of computation by combining the above mentioned methods. A motion picture compression apparatus provided with a motion estimation circuit for motion estimation by employing a combined method of the subsample and algorithmic search methods is described in xe2x80x9cA 1.5W Single-Chip MPEG2 MP@ML Encoder with Low-Power Motion Estimation and Clockingxe2x80x9d, by M. Mizuno et al., ISSCC Digest of Technical Papers, pp. 256-257, 1997, which is incorporated herein by reference.
On the other hand, an interruption method has been proposed as a method capable of statically changing the search range in accordance with an original image to be an input rather than the above described static algorithm. In the interruption method, a target difference value is preliminary set. A vector having a difference value which is smaller than the target value is detected. The vector becomes a search result if the difference value of the vector is smaller than that of the next vector. For the interruption method, xe2x80x9cAdaptive Threshold Setting for Snapping-off Motion Vector Estimation Algorithmxe2x80x9d, by Sasajima and Enomoto, The Institute of Electronics Information and Communication Engineers General Conference, p. 46, 1998 is incorporated herein by reference.
In both of subsample and algorithmic search methods which have been proposed, the vector is searched in accordance with a statically determined algorithm and not depending on the original image data to be an input. Thus, the vector having a difference value which is the same as or close to that obtained by the full sample method for all samples can be detected for a specific original image data. For another specific original image data, however, a vector having a difference value which is significantly greater than that obtained by the full sample method for all samples is detected, thereby resulting in lower compressibility of moving picture and lower image quality when the compressed moving picture is expanded.
Further, in the interruption method, although the amount of computation is reduced only by about 40% as compared with the case of the full sample method for all samples, a vector having a difference value which is, on the average, significantly greater than that obtained by the full search method is disadvantageously detected.
In addition, the conventional motion estimation apparatus is in most cases designed to operate regularly arranged circuits as high an operating efficiency as possible and in parallel, while making use of the characteristic of the LSI. Thus, the design of such apparatus is focused on increase in the operating efficiency of a calculation circuit, such as calculation of the difference value for a motion vector which is ultimately unnecessary, rather than on reduction in power consumption. As a result, power consumption for the conventional apparatus is significant though calculation performance thereof is high.
In Japanese Patent Laying-Open No. 10-191352, a motion estimation apparatus capable of interrupting computation in accordance with a comparison result with respect to a prescribed threshold value is disclosed. The apparatus is intended for high speed processing. In the apparatus, however, computation cannot be interrupted in the computation for the first position as the threshold value is calculated. Thus, if the number of candidate vectors which can be processed at a time is too large, an effect of interrupting the computation is not obtained. In addition, in this apparatus, although a prescribed threshold value can be preliminary given, properties of the threshold value are not disclosed. Therefore, setting of an optimum threshold value is difficult.
The present invention is made to solve the aforementioned problems. An object of the present invention is to provide a motion estimation method capable of setting an optimum threshold value and performing a high speed processing.
Another object of the present invention is to provide a motion estimation apparatus capable of setting an optimum threshold value and performing a high speed processing with reduced power consumption.
Still another object of the present invention is to provide a motion estimation apparatus capable of setting an optimum threshold value and performing a high speed processing with reduced power consumption and simplified internal structure.
A motion estimation method according to one aspect of the present invention includes steps of: sequentially selecting one of blocks to be searched from a search range; sequentially calculating a difference between corresponding sample values of a reference block and one of blocks to be searched and accumulating an absolute value of the difference; comparing an intermediate result of an accumulation value and a prescribed threshold value for a prescribed number of samples and interrupting the step of accumulating the absolute value of the difference when the intermediate result exceeds the prescribed threshold value; and making one of blocks to be searched having a minimum final result of the accumulation values correspond to the reference block. The prescribed threshold value is dependent on the reference block.
When the intermediate result exceeds the threshold value, the computation for that one of blocks to be searched can be interrupted. Thus, the process can immediately proceed to computation for next one of blocks to be searched. In addition, as the prescribed threshold value is dependent on the reference block, an optimum threshold value can be set for every reference block. Therefore, high speed processing is achieved.
Preferably, the step of sequentially selecting one of blocks to be searched from the search range includes a step of selecting one of blocks to be searched in the order of a position closer to the reference block.
One of blocks to be searched corresponding to the reference block can be detected in the early stage. Accordingly, calculation for accumulating difference in the following process can be interrupted in the early stage. This is because one of blocks to be searched corresponding to the reference block is generally positioned near the reference block. Thus, high speed processing can be achieved.
More preferably, the step of accumulating the absolute value of difference includes a plurality of steps each sequentially calculating a difference between corresponding sample values of the reference block and one of blocks to be searched and accumulating an absolute value of the difference for every one of plurality of blocks to be searched. The step of interrupting the step of accumulating the absolute value of difference further includes steps of: comparing an intermediate result of an accumulation value and a prescribed threshold value for a prescribed number of samples for each of the plurality of steps of accumulating the absolute value of the difference and interrupting the accumulation process when the intermediate result exceeds the prescribed threshold value; and increasing the prescribed threshold value by a given amount and again performing the plurality of steps of accumulating the absolute value of difference in parallel when the plurality of steps of accumulating the absolute value of difference are all interrupted as the intermediate result of the accumulation value exceeds the prescribed threshold value.
Calculations for accumulating differences for a plurality of blocks to be searched can be performed in parallel. In addition, even if an initial value of the threshold value is too small to allow detection of one of blocks to be searched corresponding to the reference block, a suitable threshold value can be determined by gradually increasing the threshold value. Thus, the calculation for accumulating the difference can be interrupted in the early stage, thereby allowing high speed processing.
A motion estimation apparatus according to another aspect of the present invention includes: a portion for selecting one of blocks to be searched for sequentially selecting one of blocks to be searched from a search range; an absolute difference accumulating portion for sequentially calculating a difference between corresponding sample values of a reference block and one of blocks to be searched and accumulating an absolute value of difference; an accumulating operation interrupting portion connected to an output of the absolute difference accumulating portion for comparing an intermediate result of an accumulation value and a prescribed threshold value every time when calculation of the difference between corresponding sample values of the reference block and one of blocks to be searched is performed a prescribed number of times and interrupting the operation of the absolute difference accumulating portion when the intermediate result exceeds the prescribed threshold value; and a correspondence portion making one of blocks to be searched having a minimum final result of the accumulation value corresponded to the reference block. The prescribed threshold value is dependent on the reference block.
When the intermediate result of the calculation exceeds the threshold value, the motion estimation apparatus can interrupt the calculation for that one of blocks to be searched. Thus, the motion estimation apparatus can proceed to the process for next one of blocks to be searched. In addition, as the prescribed threshold value is dependent on the reference block, the motion estimation apparatus can set an optimum threshold value for every reference block. Thus, high speed processing and reduction in power consumption can be achieved.
Preferably, the absolute difference accumulating portion includes: a subtracter receiving two sample values of the reference block and one of blocks to be searched in corresponding positions; an absolute value computing element connected to the subtracter for receiving an output from the subtracter; an accumulation register storing an accumulation value of an output from the absolute value computing element; and an adder connected to the accumulation register and the absolute value computing element for receiving an output from the absolute value computing element and a value held in the accumulating register and writing an addition result to the accumulation register.
Preferably, the portion for selecting one of blocks to be searched selects one of blocks to be searched in the order of a position closer to the reference block.
The motion estimation apparatus can detect one of blocks to be searched corresponding to the reference block in an early stage. Accordingly, the motion estimation apparatus can interrupt a calculation for accumulating difference in a following process in the early stage. This is because one of blocks to be searched corresponding to the reference block is generally positioned near the reference block. Thus, high speed processing and reduction in power consumption can be achieved.
More preferably, the prescribed threshold value is an intra evaluation value of the reference block.
As the intra evaluation value is the prescribed threshold value, determination is readily made as to whether the reference block per se is coded. More specifically, when one of blocks to be searched corresponding to the reference block is not detected, the motion estimation apparatus may code the reference block per se.
A motion estimation apparatus according to still another aspect of the present invention includes: a portion for selecting one of blocks to be searched for sequentially selecting one of blocks to be searched from a search range; a plurality of registers holding a sample value of one of blocks to be searched and receiving a value of an adjacent register; a plurality of processing portions connected to the plurality of registers for sequentially calculating a difference between corresponding sample values of a reference block and one of blocks to be searched, accumulating an absolute value of difference, comparing an accumulation value and a prescribed threshold value and interrupting an operation when the accumulation value exceeds the prescribed threshold value; a portion connected to the plurality of processing portions for storing an computation result and one of blocks to be searched corresponding to the computation result when the computation result from the processing portion is smaller than the prescribed threshold value; and a threshold value managing portion applying a prescribed threshold value to each of the plurality of processing portions, increasing the prescribed threshold value by a given amount and again applying it to the plurality of processing portions when all of the operations of the plurality of processing portions are interrupted as the accumulation value exceeds the prescribed threshold value. The prescribed threshold value is dependent on the reference block.
The motion estimation apparatus can perform calculations for accumulating differences for the plurality of blocks to be searched in parallel. In addition, even when an initial value of the threshold value is too small to allow detection of one of blocks to be searched corresponding to the reference block, the motion estimation apparatus can determine a suitable threshold value by gradually increasing the threshold value. Thus, the motion estimation apparatus can interrupt a calculation for accumulating difference in the early stage, thereby allowing high speed processing and reduction in power consumption. Further, as the prescribed threshold value is dependent on the reference block, the motion estimation apparatus can set an optimum threshold value for every reference block.
Preferably, each of the above mentioned plurality of processing portions includes: a first gate receiving a sample of the reference block; a second gate receiving a sample of one of blocks to be searched; an absolute difference sum computing element connected to the first and second gates for receiving outputs from the first and second gates; a latch connected to an output of the absolute difference sum computing element; an adder receiving an output from the latch and an accumulation value of an output from the absolute difference sum computing element; an accumulation register connected to an output of the adder for holding the accumulation value; a comparison computing element receiving a value of the accumulation register and the prescribed threshold value for outputting the value of the accumulation register and a comparison result of the value of the accumulation register and the prescribed threshold value; and a circuit connected to an output of the comparison computing element for applying a signal in accordance with a comparison result of the value of the accumulation register and the prescribed threshold value to the first and second gates.
More preferably, the prescribed threshold value is a minimum value of the final results of the accumulation values which have been obtained for a reference block in a preceding frame which is in the same position as that of the current frame.
The motion estimation apparatus sets, as the prescribed threshold value, the minimum value of the final results of the accumulation values which have been obtained for the reference block in the preceding frame which is in the same position as that of the current frame. Properties of the images in the same positions are similar even if the images are in adjacent frames. Thus, the optimum threshold value can be set.
More preferably, the motion estimation apparatus further includes a portion for detecting a scene change. The prescribed threshold value is one of a value which depends on the reference block in a current frame and that in a preceding frame, both of which are determined depending on occurrence of the scene change.
The motion estimation apparatus can set the optimum threshold value even when the scene change occurs. If the scene change occurs, a value corresponding to the reference block in the preceding frame should not be used as a threshold value. This is because the property of the image has changed due to the scene change. As a result, motion estimation apparatus can set the optimum threshold value by using the value corresponding to the current frame as the threshold value when the scene change occurs.
More preferably, the motion estimation apparatus further includes a plurality of reference value registers connected to the plurality of processing portions for holding sample data of the reference blocks.
The motion estimation apparatus can perform processes for the plurality of reference blocks in parallel by grouping the plurality of processing portions and making each group correspond to a different reference block. Thus, high speed processing and reduction in power consumption can be achieved.
More preferably, the motion estimation apparatus further includes: a bus for supplying a sample value of the reference block for the plurality of processing portions; and a plurality of threshold value registers connected to a bus and a plurality of processing portions for holding the threshold value. The bus allows transfer of the threshold value and the sample value of the reference block in first and second periods, respectively.
An internal structure of the apparatus is simplified as the bus is used both for applying the prescribed threshold value and for applying the sample value of the reference block.
The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.